752. Open the Lock 和 127. Word Ladder 都是跟搜索相關的，這裡拿來當例子的是 127。

這題其實可以想成建圖，如果兩個單字只差一個字母就有邊，然後求兩點之間的最短路徑。所以可以運用 BFS 去搜尋並設立停止條件，如果最後 queue 都找完路徑還是不存在則終止。

下面附的是提交後可以看的參考解答（效率比自己寫的高太多了）。值得一提的有兩點：第一個是這裡有用到類似雙向 BFS 的概念，可以從前往後找，也可以從後往前推，這邊是看哪邊當前的 bfs set 比較少就從那端找，很聰明的降低雜度的方法。

另外一點是，這邊其實不算有建圖，而是直接遍歷所有替換字母的可能後找路徑。找 26 個字母 * 單詞長度 n 看起來好像有點麻煩，不過建圖的話複雜度直接是 O(n^2)（這裡的 n 是單詞數量，如果考量字母長度 m，會變成 (nm)^2，而這寫法是不太可能真的需要去遍歷到圖上所有可能的邊的，可能也因此這個寫法的執行時間相對其他方法短很多吧。

# leetcode 提交頁的參考解答
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        words = set(wordList)
        if endWord not in words:
            return 0
        bs = {beginWord}
        es = {endWord}
        dis = 1

        while bs:
            words -= bs
            dis += 1
            ns = set()
            for w in bs:
                for i in range(len(w)):
                    pre = w[:i]
                    post = w[i+1:]
                    for c in string.ascii_lowercase:
                        nw = pre + c + post
                        if nw in words:
                            if nw in es:
                                return dis
                            ns.add(nw)
            bs = ns
            if len(bs) > len(es):
                bs, es = es, bs
        return 0

• 127. Word Ladder
• 752. Open the Lock